翻訳と辞書 Words near each other ・ Schwartziella robusta ・ Schwartziella sanmartini ・ Schwartziella sculpturata ・ Schwartziella similiter ・ Schwartziella sulcostriata ・ Schwartziella typica ・ Schwartziella yragoae ・ Schwartzkopff ・ Schwartzkopff torpedo ・ Schwartzkopff-Eckhardt II bogie ・ Schwartzkopffstraße (Berlin U-Bahn) ・ Schwartzman ・ Schwartzmann ・ Schwartz–Bruhat function ・ Schwartz–Jampel syndrome ・ Schwartz–Zippel lemma ・ Schwarz ・ Schwarz (surname) ・ Schwarz alternating method ・ Schwarz Gastropoden Formation ・ Schwarz greift ein ・ Schwarz Gruppe ・ Schwarz in Schwarz ・ Schwarz integral formula ・ Schwarz lemma ・ Schwarz minimal surface ・ Schwarz reflection principle ・ Schwarz Rot Gold ・ Schwarz Stein ・ Schwarz triangle Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Schwartz–Zippel lemma ： ウィキペディア英語版 Schwartz–Zippel lemma In mathematics, the Schwartz–Zippel lemma is a tool commonly used in probabilistic polynomial identity testing, i.e. in the problem of determining whether a given multivariate polynomial is the 0-polynomial (or identically equal to 0). It was discovered independently by Jack Schwartz, Richard Zippel, and Richard DeMillo and Richard J. Lipton. The finite field version of this bound was proved by Øystein Ore in 1922.〔Ö. Ore, Über höhere Kongruenzen. Norsk Mat. Forenings Skrifter Ser. I (1922), no. 7, 15 pages.〕 == Statement of the lemma == The input to the problem is an ''n''-variable polynomial over a field F. It can occur in the following forms: ; Algebraic form: For example, is : $(x\_1\; +\; 3x\_2\; -\; x\_3)(3x\_1\; +\; x\_4\; -\; 1)\; \backslash cdots\; (x\_7\; -\; x\_2)\; \backslash equiv\; 0\backslash \; ?$ To solve this, we can multiply it out and check that all the coefficients are 0. However, this takes exponential time. In general, a polynomial can be algebraically represented by an arithmetic formula or circuit. ; Determinant of a matrix with polynomial entries: Let : $p(x\_1,x\_2,\; \backslash ldots,\; x\_n)\; \backslash ,$ be the determinant of the polynomial matrix. Currently, there is no known sub-exponential time algorithm that can solve this problem deterministically. However, there are randomized polynomial algorithms for testing polynomial identities. Their analysis usually requires a bound on the probability that a non-zero polynomial will have roots at randomly selected test points. The Schwartz–Zippel lemma provides this as follows: Theorem 1 (Schwartz, Zippel). ''Let'' : $P\backslash in\; F()$ ''be a non-zero polynomial of total degree d ≥ 0 over a field, F. Let S be a finite subset of F and let r1, r2, ..., rn be selected at random independently and uniformly from S. Then'' : $\backslash Pr()\backslash leq\backslash frac.\; \backslash ,$ In the single variable case, this follows directly from the fact that a polynomial of degree ''d'' can have no more than ''d'' roots. It seems logical, then, to think that a similar statement would hold for multivariable polynomials. This is, in fact, the case. ''Proof.'' The proof is by mathematical induction on ''n''. For ''n'' = 1, as was mentioned before, ''P'' can have at most ''d'' roots. This gives us the base case. Now, assume that the theorem holds for all polynomials in ''n'' − 1 variables. We can then consider ''P'' to be a polynomial in ''x''1 by writing it as : $P(x\_1,\backslash dots,x\_n)=\backslash sum\_^d\; x\_1^i\; P\_i(x\_2,\backslash dots,x\_n).$ Since $P$ is not identically 0, there is some $i$ such that $P\_i$ is not identically 0. Take the largest such $i$. Then $\backslash deg\; P\_i\backslash leq\; d-i$, since the degree of $x\_1^iP\_i$ is at most d. Now we randomly pick $r\_2,\backslash dots,r\_n$ from $S$. By the induction hypothesis, $\backslash Pr()\backslash leq\backslash frac.$ If $P\_i(r\_2,\backslash ldots,r\_n)\backslash neq\; 0$, then $P(x\_1,r\_2,\backslash ldots,r\_n)$ is of degree $i$ so ::: $\backslash Pr(0)\backslash leq\backslash frac.$ If we denote the event $P(r\_1,r\_2,\backslash ldots,r\_n)=0$ by $A$, the event $P\_i(r\_2,\backslash ldots,r\_n)=0$ by $B$, and the complement of $B$ by $B^c$, we have +\frac=\frac. |} 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Schwartz–Zippel lemma」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.